package www.study.com;

import java.util.ArrayList;
import java.util.List;

//括号生成 https://leetcode.cn/problems/generate-parentheses/
public class code21 {
    public static void main(String[] args) {

    }

    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<String>();
            func(res,new StringBuilder(),0,0,n);
            return res;
        }

        /**
         *
         * @param res
         * @param sb
         * @param le 已经放置的左括号的个数
         * @param rg 已经放置的右括号的个数
         * @param n
         */
        public void func(List<String> res,StringBuilder sb, int le, int rg,int n){
            if(le == n && rg == n){
                res.add(sb.toString());
                return;
            }
            //还有左括号可以放置 就可以放置左括号
            if(le != n){
                sb.append('(');
                func(res,sb,le + 1,rg,n);
                sb.deleteCharAt(sb.length() - 1);
            }
            //左括号已经放置的个数大于右括号已经放置的个数，才可以放置右括号
            if(le > rg){
                sb.append(')');
                func(res,sb,le,rg + 1,n);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}
